* Print this text file with right margin 60, left margin 3
FILE: README.DOC by Kenneth E. Perry
Programming One-dimensional Cellula Automata
The theory of one-dimensional automata is described in my article in the December '86 issue of Byte magazine and will not be repeated here. That article was written in mid-1985, and does not reflect the new material discussed in this document. My interest in one-dimensional cellula automata was sparked on reading Stephen Wolfram's article "Computer Software in Science and Mathematics" in the September 1984 issue of Scientific American; about half of the article was devoted to this subject. Reading it (and especially looking at the stunning color reproductions of computer graphics) stimulated in me a strong desire to program these automata on my own computer.
My first attempt was written in Basic; this turned out to be unacceptably slow. I then bit the bullet and wrote a program that was entirely in assembly language. This program was plenty fast enough and it served me well for some time - to the present moment (spring of 1986) it has allowed me to examine between 10 and 20 thousand of the quarter million possible 4-state rules - but it had the disadvantage of being machine specific. Due to the unique color graphics routines it contained, the program would run only on a Heath/Zenith Z-100 Computer. I recently acquired a Z-200 computer, a PC-AT eqivalent, (I am fiercely loyal to Heath computers; this is my third.) and decided to rewrite my program in the PC version of Turbo Pascal which will run on any PC or equivalent. I will now describe this program, called "CELLULAR", plus two demonstration programs, "DEMO-ONE" AND "DEMO-TWO" which illustrate some of the best rules I have found over the past year or so.
USING THE CELLULAR.COM PROGRAM
When the CELLULAR program is invoked, the first thing to do is to strike the (Ins) key. This causes the first (random initialized) automaton to be displayed on the color screen; at the same time the status line will be displayed. The first ten digits are the (randomly generated) rule number; the next single integer is the background state, usually zero. This value can be changed by using the F2 key and a numeric key. It is used in the KEYBOARD INITIALIZE MODE to force a non-zero background. The last 3 digits form a decimal number indicating the width of the COMPUTE FIELD of which more later. Except for some function keys and the normal row of numeric keys, all keys that control the program are located near the right hand key-pad.
Striking the (Del) key will display the same rule with different random initialization; doing this several times often gives an insight into what the rule can do. At this point you can either continue striking (Ins) (getting more random rules) and watching the display until you find something interesting, or you can strike the F1 function key. This will erase the displayed rule and position the cursor for entry of a new rule (without spaces) using the regular numeric keys on the main keyboard. With a specific new rule entered you can proceed just the same as after a random rule was given as explained in the next paragraph.
If you follow the random search and find something interesting, shift to the (Del) and ( + ) keys to further examine the rule. The (Del) key allows you to re-examine the same rule with different random initialization of the field of cells. The ( + ) key allows examining of further generations of the automaton beyond the bottom of the screen far removed from the random initial transient where the true nature of the automaton will often show itself. You can now shift to the KEYBOARD INITIALIZE MODE by striking the ( - ) key.
In this mode, the PIXEL CURSOR will appear in the center top of the screen just below the INITIALIZE LINE which will display the color of the BACKGROUND shown on the status line. If the background is 0 there will, of course, be no visible initialize line. The left and right arrow keys will move the PIXEL CURSOR left and right. The numeric keys 0,1,2 and 3 place corresponding pixel values (black, green, red, brown) in the INITIALIZE LINE, and the PIXEL CURSOR will move one pixel to the right. If one of these keys is held down, the auto-repeat feature will cause the pixel cursor to slew to the right, laying down a string of pixels of the corresponding color. The spacing of the pixels will depend on which of the function keys, F8,F9,F10 is in control. If the line of cells overshoots the end of the screen, no harm is done. In the same way the 0 numeric key can be used to erase all color cells from the initialize line. Once the initialize line is the way you want it, press the ( * ) key to engender the automaton that is created by the rule and the initial state. In fact, this is the only way to exit the KEYBOARD INITIALIZE MODE, and no other key is effective until the screen is finished painting; this can be confusing if the screen is painting all black.
One feature of CELLULAR, in the keyboard initialize mode, that may not at first be apparent to the user is the expanding COMPUTE FIELD. This is the area in memory where the cell values are stored and recomputed before being displayed. This starts out to be the same width as the displayed field, 160 cells or 320 or whatever, but memory is set aside so that the computation field can be any width up to 4000 cells. If a structure expands so that it threatens to exceed the original field width, the computation field expands (symmetrically) to keep ahead of the structure; this width is shown on the status line. Thus, although the structure may expand out of the visual field, it is still being computed correctly, and the part that is displayed is true; edge effects are avoided. Of course, as the field width increases, the computation and display slows down, but not much since displaying the pixels takes up more time than computing. This is especially valuable in examining the developing central axis of class 4 triangles.
SUMMARY OF CELLULAR FUNCTIONS
You come up in the RANDOM SEARCH MODE
There are 3 sets of keys used to control the program
1. Seven "action" keys in the keypad area
2. Four numeric keys 0, 1, 2, 3
3. Five function keys that perform various functions
KEYPAD KEYS IN RANDOM SEARCH MODE
(Ins) Generates a new random rule and displays the screen from random initialization of the line of cell.
(Del) Dispalys the same rule again with different random initialization.
( + ) Displays more generations of the same rule.
( - ) Places you in the KEYBOARD INITIALIZE MODE. the PIXEL CURSOR appears in the center top of the screen just below the INITIALIZE LINE which will display the color of the BACKGROUND shown on the status line. If the background is 0 there will, of course, be no visible initialize line.
( <- ) and ( -> ) arrows move the PIXEL CURSOR left and right
Numeric keys 0,1,2 and 3 place corresponding pixel values (black, green, red, brown) in the INITIALIZE LINE;
( * ) Displays the structures engendered by the RULE and the contents of the INITIALIZE LINE.
FUNCTION KEYS
The following keys may be struck any time the screen is not painting. The status line will show the changes made.
F1 Erases the displayed rule (but not the first digit which is always zero) and positions the cursor for entry of a new rule using the numeric keys (type without spaces) the new rule will appear on the status line.
F2 Allows changing the background value which is usually 0 but may be set to any value 0, 1, 2, 3. using the numeric keys.
F8 Sets a screen of 80 by 50 pixels (CELLS) for a very quick look.
F9 Sets a screen of 160 by 100 pixels for a quick look.
F10 Sets a screen if 320 by 200 pixels for a better picture.
Striking return at any time when the screen is not painting, will exit from CELLULAR and return the system prompt.
DEMONSTRATION PROGRAMS DEMO-ONE AND DEMO-TWO
The demonstration programs on this disk illustrate some of the many kinds of structures that can be found in one-dimensional cellula automata.
USING DEMO-ONE
The DEMO-ONE.COM program reads a list of rules from the text file DEMO-1.DOC and displays the structures after random initialization of the line of cells. Many of these rules show a structure which I call a "Boundary Glider", a propagating structure that forms a boundary between regions of different background states.
When the DEMO-ONE program is invoked, the screen is blanked. The following keys control the program:
1. The (Ins) key will cause the structure of the first (or next) rule to be displayed after random initialization. The rule number will be displayed on the status line.
2. The (Del) key will redisplay the structure of a rule with a new random initialzion
3. The ( + ) key will continue the display of succeeding generations of the structure.
4. The F9 and F10 keys can be used to change the resolution of the display field as described above.
USING DEMO-TWO
The program DEMO-TWO.COM reads rules and initial conditions from the text file DEMO-2.DOC. This file is heavily commented, and it is a good idea to have a printout of it beside you as you go through this program. The contents of the various sections of DEMO-2.DOC are as follows:
DEMO1 Demonstration of simple cyclic structures.
DEMO2 Demonstration of more complex cyclic structures.
DEMO3 Demonstration of self similar triangles.
DEMO4 Demonstration of various kinds of gliders.
DEMO5 METHESULAS. (use the ( + ) key to follow these)
DEMO6 GLIDER GUNS.
DEMO7 CLASS 4 TRIANGLES and RETRO-FIRING GLIDERS. Speed = 1
DEMO8 CLASS 4 TRIANGLES. Speed of expansion less than 1
DEMO9 More CLASS 4 TRIANGLES. Speed = 1
When the DEMO-TWO program is envoked the status line will appear at the bottom of the screen. Operation of DEMO-TWO is similar to DEMO-ONE except that random initialization is not used, and the (Del) key has no effect. In either DEMO mode you can press F9 to go through the rules faster.
I will describe some of the structures that are to be found in DEMO-ONE and DEMO-TWO. As I mentioned, the DEMO-ONE structures are all initialized in the random state. I had been keeping a list of rules that seemed to show to best effect when randomly initialized. One day I noticed that many of these displays contained a structure that I had not recognized before and which could have only one name, "Boundary Gliders", that is, propagating structures that formed boundaries between regions of different background colors. A number of these structures will be found in DEMO-ONE and these are often responsible for very striking visual effects.
The text file DEMO-2.DOC, which supplies the rules and initial conditions for program DEMO-TWO, is rather heavily commented and is divided into 9 "chapters" DEMO1 through DEMO9. DEMO1 shows a variety of simple cyclic structures such as we have discussed before; a few are rather unusual. DEMO2 shows more complex cyclic structures of longer period.
DEMO3 shows "self-similar triangles"; these are structures that expand at a constant speed (usually the speed of light; speed = 1, but sometimes 1/2, 1/3, 2/3, etc.) and hence show a triangular structure. Within, are generated triangular forms that appear larger and larger as the the structure grows, but which all look the same except for being different in size, thus self-similar. The first three structures are truly self-similar because, if you ignore the individual pixels, there is nothing to give a scale of size. Strictly speaking, most of the other structures are not truly self-similar, but this makes then prettier, I think.
DEMO4 displays some gliders specially selected for unusual or wierd effects. Some perioically bud off other structures at a constant rate.
DEMO5 contains a number of "Methuselas", a term borrowed from the Game of Life. These structures grow very slowly and last for hundreds or thousands of generations before degenerating into a few simple cyclic structures (or dying out completely). I consider these to be the most interesting - besides being among the hardest to find - of all structures of one-dimensional cellula automata. Follow these to the end by using the ( + ) key. I think you will find it an interesting experience.
DEMO6, "Glider Guns", are stationary structures that periodically shoot off gliders. Since the stationary structures are symmetrical the gliders fire in both directions. As you go down the list you will see the pictures becomming more and more "Baroque".
CLASS 4 TRIANGLES have the the same external form as the self-similar triangles mentioned above but the internal structure is anything but self-similar. I have found so many of them that they fill DEMO7, DEMO8, and DEMO9; in fact they are the easiest to find of all the really complex class 4 structures.
Class 3 triangles, now. Well, you know, this might be a good way to introduce the game; try it. Invoke CELLULAR; strike (ins); if the display you get is not obviously class 1 or class 2, strike ( - ) then numeric key 1, 2, or 3 ( a single cell seed ) then ( * ). You should get a class 3 triangle. Sometimes the seed will not germinate, in which case try a different key. The triangle will always be symmetrical so the effects are usually more or less pretty; often quite striking.
As another way of exploring CELLULAR, I suggest using F1 to type in one of the rules from DEMO-2.DOC. Then, strike (del) for random initialization of the field of cells. You will see the screen much as I first saw it when this rule got added to my list. Do this several times with each rule and note the difference between class 3 and class 4 in this mode.
These Programs will run on any PC or compatable that has a color graphics adapter, but the pictures will paint much faster on a PC-AT (which is what I am using).
In closing I want to tell you of something that happened only yesterday (as I type this) and illustrates the sort of unexpected event that makes this game so interesting. I was giving this disk a final checkout before sending it off to Byte and running CELLULAR, not looking for anything in particular, when I happened on rule 0110223330. It belongs to a class that I call "wallpaper" which consist of structures of constant width that form vertical stripes all across the screen. These are usually rather uninteresting, but this rule is anything but that. I have never seen anything like it. I have added this rule to the end of DEMO-1.DOC. You might enjoy watching it on the screen as successive randon initializations are generated by pressing (Del).
